Chu spaces generalize the notion of

topological space In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called points ...

by dropping the requirements that the set of

open sets In mathematics, open sets are a generalization of open intervals in the real line. In a metric space (a set along with a distance defined between any two points), open sets are the sets that, with every point , contain all points that are suff ...

be closed under

union Union commonly refers to: * Trade union, an organization of workers * Union (set theory), in mathematics, a fundamental operation on sets Union may also refer to: Arts and entertainment Music * Union (band), an American rock group ** ''Un ...

and finite

intersection In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, their i ...

, that the open sets be extensional, and that the membership predicate (of points in open sets) be two-valued. The definition of

continuous function In mathematics, a continuous function is a function such that a continuous variation (that is a change without jump) of the argument induces a continuous variation of the value of the function. This means that there are no abrupt changes in value ...

remains unchanged other than having to be worded carefully to continue to make sense after these generalizations. The name is due to Po-Hsiang Chu, who originally constructed a verification of autonomous categories as a graduate student under the direction of Michael Barr in 1979.

Definition

Understood statically, a Chu space (''A'', ''r'', ''X'') over a set ''K'' consists of a set ''A'' of points, a set ''X'' of states, and a function ''r'' : ''A'' × ''X'' → ''K''. This makes it an ''A'' × ''X''

matrix Matrix most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** ''The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...

with entries drawn from ''K'', or equivalently a ''K''-valued

binary relation In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...

between ''A'' and ''X'' (ordinary binary relations being 2-valued). Understood dynamically, Chu spaces transform in the manner of topological spaces, with ''A'' as the set of points, ''X'' as the set of open sets, and ''r'' as the membership relation between them, where ''K'' is the set of all possible degrees of membership of a point in an open set. The counterpart of a continuous function from (''A'', ''r'', ''X'') to (''B'', ''s'', ''Y'') is a pair (''f'', ''g'') of functions ''f'' : ''A'' → ''B'', ''g'' : ''Y'' → ''X'' satisfying the ''adjointness condition'' ''s''(''f''(''a''), ''y'') = ''r''(''a'', ''g''(''y'')) for all ''a'' ∈ ''A'' and ''y'' ∈ ''Y''. That is, ''f'' maps points forwards at the same time as ''g'' maps states backwards. The adjointness condition makes ''g'' the inverse image function ''f''⁻¹, while the choice of ''X'' for the

codomain In mathematics, the codomain or set of destination of a function is the set into which all of the output of the function is constrained to fall. It is the set in the notation . The term range is sometimes ambiguously used to refer to either the ...

of ''g'' corresponds to the requirement for continuous functions that the inverse image of open sets be open. Such a pair is called a Chu transform or morphism of Chu spaces. A topological space (''X'', ''T'') where ''X'' is the set of points and ''T'' the set of open sets, can be understood as a Chu space (''X'',∈,''T'') over . That is, the points of the topological space become those of the Chu space while the open sets become states and the membership relation " ∈ " between points and open sets is made explicit in the Chu space. The condition that the set of open sets be closed under arbitrary (including empty) union and finite (including empty) intersection becomes the corresponding condition on the columns of the matrix. A continuous function ''f'': ''X'' → ''X between two topological spaces becomes an adjoint pair (''f'',''g'') in which ''f'' is now paired with a realization of the continuity condition constructed as an explicit witness function ''g'' exhibiting the requisite open sets in the domain of ''f''.

Categorical structure

The category of Chu spaces over ''K'' and their maps is denoted by Chu(Set, ''K''). As is clear from the symmetry of the definitions, it is a self-dual category: it is equivalent (in fact isomorphic) to its dual, the category obtained by reversing all the maps. It is furthermore a *-autonomous category with dualizing object (''K'', λ, ) where λ : ''K'' × → ''K'' is defined by λ(''k'', *) = ''k'' (Barr 1979). As such it is a model of

Jean-Yves Girard Jean-Yves Girard (; born 1947) is a French logician working in proof theory. He is the research director ( emeritus) at the mathematical institute of the University of Aix-Marseille, at Luminy. Biography Jean-Yves Girard is an alumnus of the ...

linear logic Linear logic is a substructural logic proposed by Jean-Yves Girard as a refinement of classical and intuitionistic logic, joining the dualities of the former with many of the constructive properties of the latter. Although the logic has also be ...

(Girard 1987).

Variants

The more general

enriched category In category theory, a branch of mathematics, an enriched category generalizes the idea of a category by replacing hom-sets with objects from a general monoidal category. It is motivated by the observation that, in many practical applications, the ho ...

Chu(''V'', ''k'') originally appeared in an appendix to Barr (1979). The Chu space concept originated with Michael Barr and the details were developed by his student Po-Hsiang Chu, whose master's thesis formed the appendix. Ordinary Chu spaces arise as the case ''V'' = Set, that is, when the

monoidal category In mathematics, a monoidal category (or tensor category) is a category \mathbf C equipped with a bifunctor :\otimes : \mathbf \times \mathbf \to \mathbf that is associative up to a natural isomorphism, and an object ''I'' that is both a left and r ...

''V'' is specialized to the

cartesian closed category In category theory, a category is Cartesian closed if, roughly speaking, any morphism defined on a product of two objects can be naturally identified with a morphism defined on one of the factors. These categories are particularly important in ma ...

Set of sets and their functions, but were not studied in their own right until more than a decade after the appearance of the more general enriched notion. A variant of Chu spaces, called

dialectica space Dialectica spaces are a categorical way of constructing models of linear logic. They were introduced by Valeria de Paiva, Martin Hyland's student, in her doctoral thesis, as a way of modeling both linear logic and Gödel's Dialectica interpretat ...

s, due to replaces the map condition (1) with the map condition (2): # ''s''(''f''(''a''), ''y'') = ''r''(''a'', ''g''(''y'')). # ''s''(''f''(''a''), ''y'') ≤ ''r''(''a'', ''g''(''y'')).

Universality

The category Top of topological spaces and their continuous functions embeds in Chu(Set, 2) in the sense that there exists a full and faithful functor ''F'' : Top → Chu(Set, 2) providing for each topological space (''X'', ''T'') its ''representation'' ''F''((''X'', ''T'')) = (''X'', ∈, ''T'') as noted above. This representation is moreover a ''realization'' in the sense of Pultr and Trnková (1980), namely that the representing Chu space has the same set of points as the represented topological space and transforms in the same way via the same functions. Chu spaces are remarkable for the wide variety of familiar structures they realize. Lafont and Streicher (1991) point out that Chu spaces over 2 realize both topological spaces and

coherent space In proof theory, a coherent space (also coherence space) is a concept introduced in the semantic study of linear logic. Let a set ''C'' be given. Two subsets ''S'',''T'' ⊆ ''C'' are said to be ''orthogonal'', written ''S'' ⊥ ''T'', if ''S'' ...

s (introduced by J.-Y. Girard (1987) to model linear logic), while Chu spaces over ''K'' realize any category of vector spaces over a field whose cardinality is at most that of ''K''. This was extended by

Vaughan Pratt Vaughan Pratt (born April 12, 1944) is a Professor Emeritus at Stanford University, who was an early pioneer in the field of computer science. Since 1969, Pratt has made several contributions to foundational areas such as search algorithms, sorti ...

(1995) to the realization of ''k''-ary relational structures by Chu spaces over 2^''k''. For example, the category Grp of groups and their homomorphisms is realized by Chu(Set, 8) since the group multiplication can be organized as a

ternary relation In mathematics, a ternary relation or triadic relation is a finitary relation in which the number of places in the relation is three. Ternary relations may also be referred to as 3-adic, 3-ary, 3-dimensional, or 3-place. Just as a binary relat ...

. Chu(Set, 2) realizes a wide range of "logical" structures such as semilattices, distributive lattices, complete and completely distributive lattices, Boolean algebras, complete atomic Boolean algebras, etc. Further information on this and other aspects of Chu spaces, including their application to the modeling of concurrent behavior, may be found at
Chu Spaces
'.

Applications

Automata

Chu spaces can serve as a model of concurrent computation in

automata theory Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word ''automata'' comes from the Greek word αὐτόματο� ...

to express branching time and true concurrency. Chu spaces exhibit the quantum mechanical phenomena of complementarity and uncertainty. The complementarity arises as the duality of information and time, automata and schedules, and states and events. Uncertainty arises when a measurement is defined to be a

morphism In mathematics, particularly in category theory, a morphism is a structure-preserving map from one mathematical structure to another one of the same type. The notion of morphism recurs in much of contemporary mathematics. In set theory, morphisms a ...

such that increasing structure in the observed object reduces the clarity of observation. This uncertainty can be calculated numerically from its form factor to yield the usual

Heisenberg uncertainty In quantum mechanics, the uncertainty principle (also known as Heisenberg's uncertainty principle) is any of a variety of mathematical inequalities asserting a fundamental limit to the accuracy with which the values for certain pairs of physic ...

relation. Chu spaces correspond to wavefunctions as vectors of

Hilbert space In mathematics, Hilbert spaces (named after David Hilbert) allow generalizing the methods of linear algebra and calculus from (finite-dimensional) Euclidean vector spaces to spaces that may be infinite-dimensional. Hilbert spaces arise natural ...

References

External links

* ''Guide to Papers on Chu Spaces''
Web page
Category theory Topology